package leetcode_201_300;

import sun.security.provider.Sun;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LeeCode_209 {
    public static void main(String[] args) {
//        System.out.println(minSubArrayLen(4, new int[]{1,4,4}));
//        System.out.println(minSubArrayLen2(11, new int[]{1,1,1,1,1,1,1,1}));
        System.out.println(minSubArrayLen2(7, new int[]{2,3,1,2,4,3}));
    }

    private static int minSubArrayLen2(int target, int[] nums) {
        int n = nums.length;
        int[] sums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
        int l = 0, r = 0;
        int res = Integer.MAX_VALUE;
        while (true){
            while (r <= n && sums[r] - sums[l] < target){
                r++;
            }
            if (r > n)
                break;
            res = Math.min(res, r - l);
            l++;
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

    private static int minSubArrayLen(int target, int[] nums) {
        long n = nums.length;
        long[] sums = new long[(int) (n + 1)];
        for (int i = 0; i < nums.length; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
        int res = Integer.MAX_VALUE;
        for (long i = 1; i <= n; i++) {
            long goal = sums[(int) (i - 1)] + target;
            int bound = Arrays.binarySearch(sums, goal);
            bound = bound < 0 ? -bound - 1 : bound;
            if (bound >= sums.length)
                break;
            res = (int) Math.min(res, bound - i + 1);
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}
